/**
 * Copyright (c) 2010 Claudio Imbrenda.
 * This program is released under the terms of the GNU GPL License, version 3 or later.
 */

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <sys/mman.h>
#include "visit.h"

int targetmin = -1;
int targetmax = -1;

/* Simple sampling method */
int samplingmethod(struct tngraph*g,int iterations,int k,int*min,int*max){
 int*res; /* minimum distances */
 int best=0; /* number of iterations for the best result */
 int u,l,tmp,cx;
 uint r;
 res=malloc(g->size * sizeof(int));
 
 for(cx=0;cx<iterations;cx++){
  u=65536,l=0; /* best upper and lower bounds in this iteration */
  r=getrandomnode(g);
  visit(g,res,1,&r,NULL,NULL,NULL,NULL);
  tmp=arraymax(g->size,res);
  l=tmp;
  u=2*tmp;

  fprintf(ERR,"  iteration %d: (%d,%d)\n",cx,l,u);

 /* update the results */
  if(*min<l){best=cx;bestvisit=visits;*min=l;il(l);}
  if(*max>u){best=cx;bestvisit=visits;*max=u;iu(u);}
  printf("ITER #%d, visits %d: (%d,%d); best: [%d,%d]; timestamp: %lld\n",cx,visits,l,u,*min,*max,(long long)time(NULL));
  fflush(stdout);
 }
 
 free(res);
 return best;
}


static uint getmiddlenode(uint*tree, int*d, uint idx, int dist){
 uint res=idx;
 while(d[res]>(dist/2)){
  res=tree[res];
 }  
 return res;
}

/* median visit method */
int medianvisitmethod(struct tngraph*g,int iterations,int k,int*min,int*max){
 int*res;
 int u,l,cx,tmp;
 int best=0;
 uint a,b,m,r,t;
 uchar*marks = MALLOCMARKS(g->size);
 res=malloc(g->size * sizeof(int));
 uint*tree;
 tree=malloc(g->size * sizeof(uint));
 
 for(cx=0;cx<iterations;cx++){
  u=65536,l=0;
  
  /* perform a double sweep */
  r=getrandomnode(g);
  visit(g,res,1,&r,NULL,NULL,NULL,NULL);
  a=highestnonvisitedindex(g->size,res,marks);
  MARKNODE(a,marks);
  tmp=res[a];
  l=tmp;il(l);
  
  b=visit(g,res,1,&a,NULL,tree,NULL,NULL);
  tmp=res[b];
  if(tmp>l){l=tmp;il(l);}
  if(2*tmp<u){u=2*tmp;iu(u);}
  
  /* get the median node and perform a visit from there */
  m=getmiddlenode(tree,res,b,tmp);
  t=visit(g,res,1,&m,NULL,NULL,NULL,NULL);
  tmp=res[t];
  if(tmp>l){l=tmp;il(l);}
  if(2*tmp<u){u=2*tmp;iu(u);}
  
  /* update the bounds */
  fprintf(ERR,"  iteration %d: (%d,%d)\n",cx,l,u);  
  if(*min<l){best=cx;bestvisit=visits;*min=l;}
  if(*max>u){best=cx;bestvisit=visits;*max=u;}
  printf("ITER #%d, visits %d: (%d,%d); best: [%d,%d]; timestamp: %lld\n",cx,visits,l,u,*min,*max,(long long)time(NULL));
  fflush(stdout);

  /* if we found the actual diameter, we can quit */
  if((*min)==(*max)) break;
 }
 free(marks);
 free(tree);
 free(res);
 return best;
}

/* median node visit tree method */
int mediantreemethod(struct tngraph*g,int iterations,int k,int*min,int*max){
 int*res;
 int u,l,cx,tmp;
 int best=0;
 uint a,b,c,m,i,r;
 res=malloc(g->size * sizeof(int));
 uchar*marks = MALLOCMARKS(g->size);
 uint*tree = malloc(g->size*sizeof(uint));
 
 for(cx=0;cx<iterations;cx++){
  u=65536,l=0;
  
  /* double sweep */
  r=getrandomnode(g);
  visit(g,res,1,&r,NULL,NULL,NULL,NULL); 
  a=highestnonvisitedindex(g->size,res,marks);
  MARKNODE(a,marks);
  tmp=res[a];
  l=tmp;il(l);
  
  b=visit(g,res,1,&a,NULL,tree,NULL,NULL);
  tmp=res[b];
  if(tmp>l){l=tmp;il(l);}
  if(2*tmp<u){u=2*tmp;iu(u);}
  
  m=getmiddlenode(tree,res,b,tmp);
  fprintf(ERR,"middle node:%d\n",m);
  
  /* make the tree from m */
  c=visit(g,res,1,&m,NULL,tree,NULL,NULL);
  
  /* compute the diameter of the spanning tree */
  i=visit(g,res,1,&c,NULL,NULL,NULL,tree);
  if(u>res[i]){u=res[i];iu(u);}

  fprintf(ERR,"  iteration %d: (%d,%d)\n",cx,l,u);
  
  /* update the bounds */
  if(*min<l){best=cx;bestvisit=visits;*min=l;}
  if(*max>u){best=cx;bestvisit=visits;*max=u;}
  printf("ITER #%d, visits %d: (%d,%d); best: [%d,%d]; timestamp: %lld\n",cx,visits,l,u,*min,*max,(long long)time(NULL));
  fflush(stdout);

  /* if we found the actual diameter, we can quit */
  if((*min) == (*max))break;
 }
 free(marks);
 free(tree);
 free(res);
 return best;
}



/** Counts the number ot times that a value occours in an array
 @param s the size of the array
 @param a the array
 @param n the value
*/
static uint count(uint s, int*a, uint n){
 uint res=0;
 uint cx;
 
 for(cx=0;cx<s;cx++)
   if(a[cx]==n)res++;
 return res;
}

/** Puts in the output array the indexes of the elements that have a specific value in the input array.
 @param s size of the input array
 @param a the input array
 @param n the value
 @param dest the output array. It MUST be big ebough to contain all the elements.
*/
static void grep(uint s, int*a, uint n, uint*dest){
 uint cx,sp;
 
 for(cx=0,sp=0;cx<s;cx++)
   if(a[cx]==n)
     dest[sp++]=cx;
}


/* fringe algorithm */
int fringemethod(struct tngraph*g, int iterations,int k, int*min, int*max){
 int*res;
 int flag=0,best=0;
 int u,l,cx,dx,tmp;
 uint a,b,c,m,i,cnt,d,r;
 uint*ttt,*tree;
 unsigned char*marks=MALLOCMARKS(g->size);
 res=malloc(g->size * sizeof(int));
 marks=MALLOCMARKS(g->size);
 tree=malloc(g->size * sizeof(uint));
 
 for(cx=0;cx<iterations;cx++){
  u=65536,l=0;
  
  /* visit limit reached */
  if(maxvisits<=visits+3){
   fprintf(ERR," maxvisits: %d, visits: %d; quitting now.\n",maxvisits,visits);
   break;
  }
  
  /* double sweep */
  r=getrandomnode(g);
  visit(g,res,1,&r,NULL,NULL,NULL,NULL);
  a=highestnonvisitedindex(g->size,res,marks);
  MARKNODE(a,marks);
  tmp=res[a];
  l=tmp;il(l);
  
  b=visit(g,res,1,&a,NULL,tree,NULL,NULL);
  tmp=res[b];
  if(tmp>l){l=tmp;il(l);}
  if(2*tmp<u){u=2*tmp;iu(u);}
  
  m=getmiddlenode(tree,res,b,tmp);
  
  if(ISMARKED(m,marks)) goto cont;
  
  /* spanning tree from the median node */
  c=visit(g,res,1,&m,NULL,tree,NULL,NULL);  
  tmp=res[c];
  if(tmp>l){l=tmp;il(l);}
  if(2*tmp<u){u=2*tmp;iu(u);}
  
  MARKNODE(m,marks);
  d=tmp-1;
  /* counts the nodes of the fringe */
  cnt=count(g->size,res,tmp);
  ttt=malloc(sizeof(uint)*cnt);
  /* Take all the nodes in the fringe */
  grep(g->size,res,d+1,ttt); 
  
  /* compute the diameter of the spanning tree */
  i=visit(g,res,1,&c,NULL,NULL,NULL,tree);
  tmp=res[i];
  if(tmp<u){fprintf(ERR,"###");u=tmp;iu(u);}
  if(l==u)goto cont1; /* actual diameter found! */

  fprintf(ERR,"# %u peripheral nodes.  ",cnt);
  /* I should do more visits than allowed per-iteration, so we skip to the next iteration */
  if(cnt>k-3){fprintf(ERR," there's no hope! k=%d.\n",k);goto cont;}
  /* I should do more visits than allowed globally, so we skip to the next iteration */
  if(visits+cnt>=maxvisits){fprintf(ERR," there's no hope! maxvisits=%d, visits=%d.\n",maxvisits,visits);goto cont;}
  
  /* If the best possible improvement is not enough, we avoid wasting visits, and skip to the next iteration */
  if((2*d)>=*max){
   fprintf(ERR,"#the best I can do is %d; I can't beat %d; there's no hope.\n",2*d,*max);
   goto cont;
  }
  
  /* for each peripheral node */
  flag=0;
  for(dx=0;dx<cnt;dx++){
    fprintf(ERR,"%d, ",dx);
    /* visit from that node */
    i=visit(g,res,1,&(ttt[dx]),NULL,NULL,NULL,NULL);
    tmp=res[i]; /* this is the eccentricity of the node ttt[dx] */
    
    /* always try to improve the lower bound */
    if(tmp>l){l=tmp;il(l);}
    if(2*tmp<u)abort(); /* should NEVER happen! */
    if(l==u)goto cont1; /* actual diameter found! */
    
    if(tmp>(2*d+1)) goto cont1;
    if(tmp>(2*d)){
     flag=1;
     if((2*d+1)>=*max){
      fprintf(ERR,"#the best I can do is %d; I can't beat %d; there's no hope.\n",2*d+1,*max);
      goto cont1;
     }
    }
  }
  
  /* Check if the eccentricity of every peripheral node is not greater thant 2*d+1 or 2*d  */
  if(flag){
   if((2*d+1)<u){u=2*d+1;iu(u);}
   fprintf(ERR,"posso abbassare di uno.\n");
  }else{
   if((2*d)<u){u=2*d;iu(u);}
   fprintf(ERR,"WOW.. posso abbassare di due!\n");
  }
  if(!flag)fprintf(ERR,"   ****  dal nodo %d la distanza reciproca tra tutti i nodi periferici sembrerebbe %d.\n",c,2*d);


cont1:
  free(ttt);
cont:
  fprintf(ERR,"  iteration %d: (%d,%d)\n\n",cx,l,u);
  
  if(*min<l){best=cx;bestvisit=visits;*min=l;}
  if(*max>u){best=cx;bestvisit=visits;*max=u;}
  printf("ITER #%d, visits %d: (%d,%d); best: [%d,%d]; timestamp: %lld\n",cx,visits,l,u,*min,*max,(long long)time(NULL));
  fflush(stdout);
  if(*min==*max)break;
 }
 
 free(marks);
 free(tree);
 free(res);
 return best;
}


int exhaustivemethod(struct tngraph*g, int iterations, int k, int*min, int*max){
 int *res = malloc(g->size * sizeof(int));
 int i,l=0,u;
 uint cx;
 
 for(cx=0;cx<g->size;cx++){
 if(GETNODE(g,cx)==NULL)continue;
  i=visit(g,res,1,&cx,NULL,NULL,NULL,NULL);
  l=res[i];
  u=2*res[i];  
  
  if(l>*min)*min=l;
  if(u<*max)*max=u;
  printf("ITER #%d;  visits %d: (%d,%d);  best: [%d,%d]; timestamp: %lld\n",cx,visits,l,u,*min,*max,(long long)time(NULL));
  fflush(stdout);
 }
 u=l;
 printf("ITER #%d;  visits %d: (%d,%d);  best: [%d,%d]; timestamp: %lld\n",cx,visits,l,u,*min,*max,(long long)time(NULL));
 
 free(res);
 return 0;
}
